/*-------------------------------------------------------------------------
 *
 * gistsplit.c
 *	  多列页面拆分算法
 *
 * 本文件关注于在多列GiST索引中做出良好的页面拆分决策。
 * 特定操作类的picksplit函数只能根据单个列产生答案。
 * 我们首先对列1运行picksplit函数；然后，如果有更多列，我们检查是否有元组在列1拆分方面是“无关紧要”的
 * （也就是说，它们可以无需额外惩罚而归到任何一侧）。如果是这样，我们尝试根据下一个列重新分配这些元组。
 * 重复直到用完所有列。
 *
 * gistSplitByKey()是此文件的入口点。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/gist/gistsplit.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/gist_private.h"
#include "utils/rel.h"

typedef struct
{
	OffsetNumber *entries;
	int			len;
	Datum	   *attr;
	bool	   *isnull;
	bool	   *dontcare;
} GistSplitUnion;


/*
 * 在 gsvp->entries[] 中列出的 itvec[] 条目中形成子键的并集，
 * 忽略 gsvp->dontcare[] 中标记的元组。  gistunionsubkey 的子例程。
 */
static void fc_gistunionsubkeyvec(GISTSTATE *fc_giststate, IndexTuple *fc_itvec,
				   GistSplitUnion *fc_gsvp)
{
	IndexTuple *fc_cleanedItVec;
	int			fc_i,
				fc_cleanedLen = 0;

	fc_cleanedItVec = (IndexTuple *) palloc(sizeof(IndexTuple) * fc_gsvp->len);

	for (fc_i = 0; fc_i < fc_gsvp->len; fc_i++)
	{
		if (fc_gsvp->dontcare && fc_gsvp->dontcare[fc_gsvp->entries[fc_i]])
			continue;

		fc_cleanedItVec[fc_cleanedLen++] = fc_itvec[fc_gsvp->entries[fc_i] - 1];
	}

	gistMakeUnionItVec(fc_giststate, fc_cleanedItVec, fc_cleanedLen,
					   fc_gsvp->attr, fc_gsvp->isnull);

	pfree(fc_cleanedItVec);
}

/*
 * 在页面分裂后重新计算左侧和右侧子键的并集，
 * 忽略 spl->spl_dontcare[] 中标记的元组。
 *
 * 注意：我们总是为所有索引列重新计算并集键。 在某些情况下，
 * 这可能会对最左侧列造成重复工作，但假设“移动元组的零惩罚”
 * 意味着“并集键完全不变”并不安全。 惩罚函数并不是 100% 准确。
 */
static void fc_gistunionsubkey(GISTSTATE *fc_giststate, IndexTuple *fc_itvec, GistSplitVector *fc_spl)
{
	GistSplitUnion fc_gsvp;

	fc_gsvp.dontcare = fc_spl->spl_dontcare;

	fc_gsvp.entries = fc_spl->splitVector.spl_left;
	fc_gsvp.len = fc_spl->splitVector.spl_nleft;
	fc_gsvp.attr = fc_spl->spl_lattr;
	fc_gsvp.isnull = fc_spl->spl_lisnull;

	fc_gistunionsubkeyvec(fc_giststate, fc_itvec, &fc_gsvp);

	fc_gsvp.entries = fc_spl->splitVector.spl_right;
	fc_gsvp.len = fc_spl->splitVector.spl_nright;
	fc_gsvp.attr = fc_spl->spl_rattr;
	fc_gsvp.isnull = fc_spl->spl_risnull;

	fc_gistunionsubkeyvec(fc_giststate, fc_itvec, &fc_gsvp);
}

/*
 * 找到标记为“不关心”的元组，即在有关 attno 列的情况下，
 * 可以以零惩罚移动到分裂的另一侧。
 *
 * 不关心的元组通过将 spl->spl_dontcare[] 中的相应条目设置为“true”来标记。
 * 调用者必须将该数组初始化为零。
 *
 * 返回找到的不关心的元组数量。
 */
static int fc_findDontCares(Relation fc_r, GISTSTATE *fc_giststate, GISTENTRY *fc_valvec,
			  GistSplitVector *fc_spl, int fc_attno)
{
	int			fc_i;
	GISTENTRY	fc_entry;
	int			fc_NumDontCare = 0;

	/*
	 * 首先，搜索左侧元组以查看是否有任何元组可以以零惩罚
	 * 添加到右侧并集键。
	 *
	 * attno 列已知为全不为空（参见 gistSplitByKey），因此我们不需要
	 * 检查空值。
	 */
	gistentryinit(fc_entry, fc_spl->splitVector.spl_rdatum, fc_r, NULL,
				  (OffsetNumber) 0, false);
	for (fc_i = 0; fc_i < fc_spl->splitVector.spl_nleft; fc_i++)
	{
		int			fc_j = fc_spl->splitVector.spl_left[fc_i];
		float		fc_penalty = gistpenalty(fc_giststate, fc_attno, &fc_entry, false,
										  &fc_valvec[fc_j], false);

		if (fc_penalty == 0.0)
		{
			fc_spl->spl_dontcare[fc_j] = true;
			fc_NumDontCare++;
		}
	}

	/* 对于右侧元组同样适用 */
	gistentryinit(fc_entry, fc_spl->splitVector.spl_ldatum, fc_r, NULL,
				  (OffsetNumber) 0, false);
	for (fc_i = 0; fc_i < fc_spl->splitVector.spl_nright; fc_i++)
	{
		int			fc_j = fc_spl->splitVector.spl_right[fc_i];
		float		fc_penalty = gistpenalty(fc_giststate, fc_attno, &fc_entry, false,
										  &fc_valvec[fc_j], false);

		if (fc_penalty == 0.0)
		{
			fc_spl->spl_dontcare[fc_j] = true;
			fc_NumDontCare++;
		}
	}

	return fc_NumDontCare;
}

/*
 * 从长度为 *len 的元组索引数组 a[] 中移除标记为不关心的元组。
 * 这分别应用于 spl_left 和 spl_right 数组。
 */
static void fc_removeDontCares(OffsetNumber *fc_a, int *fc_len, const bool *fc_dontcare)
{
	int			fc_origlen,
				fc_newlen,
				fc_i;
	OffsetNumber *fc_curwpos;

	fc_origlen = fc_newlen = *fc_len;
	fc_curwpos = fc_a;
	for (fc_i = 0; fc_i < fc_origlen; fc_i++)
	{
		OffsetNumber fc_ai = fc_a[fc_i];

		if (fc_dontcare[fc_ai] == false)
		{
			/* 将项重新输出到 a[] */
			*fc_curwpos = fc_ai;
			fc_curwpos++;
		}
		else
			fc_newlen--;
	}

	*fc_len = fc_newlen;
}

/*
 * 根据将元组合并到先前计算的并集键中的惩罚最小的一侧，
 * 将单个不关心的元组放入分裂的左侧或右侧。 我们只需考虑从
 * attno 开始的列。
 */
static void fc_placeOne(Relation fc_r, GISTSTATE *fc_giststate, GistSplitVector *fc_v,
		 IndexTuple fc_itup, OffsetNumber fc_off, int fc_attno)
{
	GISTENTRY	fc_identry[INDEX_MAX_KEYS];
	bool		fc_isnull[INDEX_MAX_KEYS];
	bool		fc_toLeft = true;

	gistDeCompressAtt(fc_giststate, fc_r, fc_itup, NULL, (OffsetNumber) 0,
					  fc_identry, fc_isnull);

	for (; fc_attno < fc_giststate->nonLeafTupdesc->natts; fc_attno++)
	{
		float		fc_lpenalty,
					fc_rpenalty;
		GISTENTRY	fc_entry;

		gistentryinit(fc_entry, fc_v->spl_lattr[fc_attno], fc_r, NULL, 0, false);
		fc_lpenalty = gistpenalty(fc_giststate, fc_attno, &fc_entry, fc_v->spl_lisnull[fc_attno],
							   fc_identry + fc_attno, fc_isnull[fc_attno]);
		gistentryinit(fc_entry, fc_v->spl_rattr[fc_attno], fc_r, NULL, 0, false);
		fc_rpenalty = gistpenalty(fc_giststate, fc_attno, &fc_entry, fc_v->spl_risnull[fc_attno],
							   fc_identry + fc_attno, fc_isnull[fc_attno]);

		if (fc_lpenalty != fc_rpenalty)
		{
			if (fc_lpenalty > fc_rpenalty)
				fc_toLeft = false;
			break;
		}
	}

	if (fc_toLeft)
		fc_v->splitVector.spl_left[fc_v->splitVector.spl_nleft++] = fc_off;
	else
		fc_v->splitVector.spl_right[fc_v->splitVector.spl_nright++] = fc_off;
}

#define SWAPVAR( s, d, t ) \
do {	\
	(t) = (s); \
	(s) = (d); \
	(d) = (t); \
} while(0)

/*
 * 当我们进行了次级分裂，但用户定义的 PickSplit
 * 方法不支持它时进行清理（导致 spl_ldatum_exists 或 spl_rdatum_exists
 * 为 true）。
 *
 * 我们考虑是否交换次级分裂的左右输出； 如果将这些元组合并到
 * 先前选择的集合中的惩罚较低，这样做可能是值得的。
 *
 * 在任何情况下，我们必须通过加入先前的并集键（oldL/oldR）来更新
 * 当前列的并集数据，因为用户定义的 PickSplit 方法没有这样做。
 */
static void fc_supportSecondarySplit(Relation fc_r, GISTSTATE *fc_giststate, int fc_attno,
					  GIST_SPLITVEC *fc_sv, Datum fc_oldL, Datum fc_oldR)
{
	bool		fc_leaveOnLeft = true,
				fc_tmpBool;
	GISTENTRY	fc_entryL,
				fc_entryR,
				fc_entrySL,
				fc_entrySR;

	gistentryinit(fc_entryL, fc_oldL, fc_r, NULL, 0, false);
	gistentryinit(fc_entryR, fc_oldR, fc_r, NULL, 0, false);
	gistentryinit(fc_entrySL, fc_sv->spl_ldatum, fc_r, NULL, 0, false);
	gistentryinit(fc_entrySR, fc_sv->spl_rdatum, fc_r, NULL, 0, false);

	if (fc_sv->spl_ldatum_exists && fc_sv->spl_rdatum_exists)
	{
		float		fc_penalty1,
					fc_penalty2;

		fc_penalty1 = gistpenalty(fc_giststate, fc_attno, &fc_entryL, false, &fc_entrySL, false) +
			gistpenalty(fc_giststate, fc_attno, &fc_entryR, false, &fc_entrySR, false);
		fc_penalty2 = gistpenalty(fc_giststate, fc_attno, &fc_entryL, false, &fc_entrySR, false) +
			gistpenalty(fc_giststate, fc_attno, &fc_entryR, false, &fc_entrySL, false);

		if (fc_penalty1 > fc_penalty2)
			fc_leaveOnLeft = false;
	}
	else
	{
		GISTENTRY  *fc_entry1 = (fc_sv->spl_ldatum_exists) ? &fc_entryL : &fc_entryR;
		float		fc_penalty1,
					fc_penalty2;

		/*
		 * 仅定义了一个先前的并集，因此我们只需通过最低惩罚选择
		 * 交换与否。 只有在次级分裂的元组中其列全部为 NULL 时，
		 * 我们才能到达这里。 
		 * （注意，在 gistSplitByKey 中的空检查不会阻止这种情况，
		 * 因为它们只会检查在外部递归级别中被认为是
		 * 不关心的元组，而不是用于确定传递的左侧和右侧并集键
		 * 的元组。）
		 */
		fc_penalty1 = gistpenalty(fc_giststate, fc_attno, fc_entry1, false, &fc_entrySL, false);
		fc_penalty2 = gistpenalty(fc_giststate, fc_attno, fc_entry1, false, &fc_entrySR, false);

		if (fc_penalty1 < fc_penalty2)
			fc_leaveOnLeft = fc_sv->spl_ldatum_exists;
		else
			fc_leaveOnLeft = fc_sv->spl_rdatum_exists;
	}

	if (fc_leaveOnLeft == false)
	{
		/*
		 * 交换左侧和右侧
		 */
		OffsetNumber *fc_off,
					fc_noff;
		Datum		fc_datum;

		SWAPVAR(fc_sv->spl_left, fc_sv->spl_right, fc_off);
		SWAPVAR(fc_sv->spl_nleft, fc_sv->spl_nright, fc_noff);
		SWAPVAR(fc_sv->spl_ldatum, fc_sv->spl_rdatum, fc_datum);
		gistentryinit(fc_entrySL, fc_sv->spl_ldatum, fc_r, NULL, 0, false);
		gistentryinit(fc_entrySR, fc_sv->spl_rdatum, fc_r, NULL, 0, false);
	}

	if (fc_sv->spl_ldatum_exists)
		gistMakeUnionKey(fc_giststate, fc_attno, &fc_entryL, false, &fc_entrySL, false,
						 &fc_sv->spl_ldatum, &fc_tmpBool);

	if (fc_sv->spl_rdatum_exists)
		gistMakeUnionKey(fc_giststate, fc_attno, &fc_entryR, false, &fc_entrySR, false,
						 &fc_sv->spl_rdatum, &fc_tmpBool);

	fc_sv->spl_ldatum_exists = fc_sv->spl_rdatum_exists = false;
}

/*
 * 微不足道的 picksplit 实现。仅在用户定义的 picksplit 将所有键放在分割同一侧时调用此函数。
 * 这属于用户定义的 picksplit 的错误，但我们不想失败。
 */
static void fc_genericPickSplit(GISTSTATE *fc_giststate, GistEntryVector *fc_entryvec, GIST_SPLITVEC *fc_v, int fc_attno)
{
	OffsetNumber fc_i,
				fc_maxoff;
	int			fc_nbytes;
	GistEntryVector *fc_evec;

	fc_maxoff = fc_entryvec->n - 1;

	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);

	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_nleft = fc_v->spl_nright = 0;

	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		if (fc_i <= (fc_maxoff - FirstOffsetNumber + 1) / 2)
		{
			fc_v->spl_left[fc_v->spl_nleft] = fc_i;
			fc_v->spl_nleft++;
		}
		else
		{
			fc_v->spl_right[fc_v->spl_nright] = fc_i;
			fc_v->spl_nright++;
		}
	}

	/*
	 * 为每一侧形成联合数据项
	 */
	fc_evec = palloc(sizeof(GISTENTRY) * fc_entryvec->n + GEVHDRSZ);

	fc_evec->n = fc_v->spl_nleft;
	memcpy(fc_evec->vector, fc_entryvec->vector + FirstOffsetNumber,
		   sizeof(GISTENTRY) * fc_evec->n);
	fc_v->spl_ldatum = FunctionCall2Coll(&fc_giststate->unionFn[fc_attno],
									  fc_giststate->supportCollation[fc_attno],
									  PointerGetDatum(fc_evec),
									  PointerGetDatum(&fc_nbytes));

	fc_evec->n = fc_v->spl_nright;
	memcpy(fc_evec->vector, fc_entryvec->vector + FirstOffsetNumber + fc_v->spl_nleft,
		   sizeof(GISTENTRY) * fc_evec->n);
	fc_v->spl_rdatum = FunctionCall2Coll(&fc_giststate->unionFn[fc_attno],
									  fc_giststate->supportCollation[fc_attno],
									  PointerGetDatum(fc_evec),
									  PointerGetDatum(&fc_nbytes));
}

/*
 * 调用用户的 picksplit 方法对 attno 列进行切分，分割元组为两个向量。
 *
 * 如果分割完成（没有更多的索引列，或者因为分割已经是最优的而不需要考虑它们），则返回 false。
 *
 * 如果 picksplit 结果是退化的（所有元组似乎都是不关心的），则返回 true 且 v->spl_dontcare = NULL，因此我们应该忽略这一列，而转而对下一列进行分割。
 *
 * 如果存在可以根据下一列重新定位的无需关心的元组，则返回 true 且 v->spl_dontcare != NULL。无需关心的元组已从分割中移除，必须由调用方重新插入。
 * 每一侧至少有一个非不关心的元组，并且更新所有列的联合键以仅包含这些元组。
 *
 * true 结果意味着至少还有一列索引。
 */
static bool fc_gistUserPicksplit(Relation fc_r, GistEntryVector *fc_entryvec, int fc_attno, GistSplitVector *fc_v,
				  IndexTuple *fc_itup, int fc_len, GISTSTATE *fc_giststate)
{
	GIST_SPLITVEC *fc_sv = &fc_v->splitVector;

	/*
	 * 准备 spl_ldatum/spl_rdatum/spl_ldatum_exists/spl_rdatum_exists，
	 * 以防我们正在进行二次分割（请参见 gist.h 中的注释）。
	 */
	fc_sv->spl_ldatum_exists = !(fc_v->spl_lisnull[fc_attno]);
	fc_sv->spl_rdatum_exists = !(fc_v->spl_risnull[fc_attno]);
	fc_sv->spl_ldatum = fc_v->spl_lattr[fc_attno];
	fc_sv->spl_rdatum = fc_v->spl_rattr[fc_attno];

	/*
	 * 让特定于操作类的 PickSplit 方法执行其功能。注意，此时我们知道 entryvec 中没有空键。
	 */
	FunctionCall2Coll(&fc_giststate->picksplitFn[fc_attno],
					  fc_giststate->supportCollation[fc_attno],
					  PointerGetDatum(fc_entryvec),
					  PointerGetDatum(fc_sv));

	if (fc_sv->spl_nleft == 0 || fc_sv->spl_nright == 0)
	{
		/*
		 * 用户定义的 picksplit 未能创建实际的分割，即它将所有内容放在同一侧。抱怨，但要应对。
		 */
		ereport(DEBUG1,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("picksplit method for column %d of index \"%s\" failed",
						fc_attno + 1, RelationGetRelationName(fc_r)),
				 errhint("The index is not optimal. To optimize it, contact a developer, or try to use the column as the second one in the CREATE INDEX command.")));

		/*
		 * 重新初始化 GIST_SPLITVEC。尽管这些字段不被 genericPickSplit() 使用，但仍要为进一步处理设置它们。
		 */
		fc_sv->spl_ldatum_exists = !(fc_v->spl_lisnull[fc_attno]);
		fc_sv->spl_rdatum_exists = !(fc_v->spl_risnull[fc_attno]);
		fc_sv->spl_ldatum = fc_v->spl_lattr[fc_attno];
		fc_sv->spl_rdatum = fc_v->spl_rattr[fc_attno];

		/* 执行通用分割 */
		fc_genericPickSplit(fc_giststate, fc_entryvec, fc_sv, fc_attno);
	}
	else
	{
		/* 为兼容旧的 picksplit API 而做的黑客 */
		if (fc_sv->spl_left[fc_sv->spl_nleft - 1] == InvalidOffsetNumber)
			fc_sv->spl_left[fc_sv->spl_nleft - 1] = (OffsetNumber) (fc_entryvec->n - 1);
		if (fc_sv->spl_right[fc_sv->spl_nright - 1] == InvalidOffsetNumber)
			fc_sv->spl_right[fc_sv->spl_nright - 1] = (OffsetNumber) (fc_entryvec->n - 1);
	}

	/* 如果 PickSplit 没有处理二次分割，则进行清理 */
	if (fc_sv->spl_ldatum_exists || fc_sv->spl_rdatum_exists)
		fc_supportSecondarySplit(fc_r, fc_giststate, fc_attno, fc_sv,
							  fc_v->spl_lattr[fc_attno], fc_v->spl_rattr[fc_attno]);

	/* 将 PickSplit 计算的联合数据项发回 v 数组 */
	fc_v->spl_lattr[fc_attno] = fc_sv->spl_ldatum;
	fc_v->spl_rattr[fc_attno] = fc_sv->spl_rdatum;
	fc_v->spl_lisnull[fc_attno] = false;
	fc_v->spl_risnull[fc_attno] = false;

	/*
	 * 如果索引列仍然存在，则考虑是否可以通过使用它们来改善分割。
	 */
	fc_v->spl_dontcare = NULL;

	if (fc_attno + 1 < fc_giststate->nonLeafTupdesc->natts)
	{
		int			fc_NumDontCare;

		/*
		 * 快速检查左侧和右侧的联合键是否相等；
		 * 如果相等，则分割肯定是退化的，因此告知调用方以下一列重新分割。
		 */
		if (gistKeyIsEQ(fc_giststate, fc_attno, fc_sv->spl_ldatum, fc_sv->spl_rdatum))
			return true;

		/*
		 * 查找不关心的元组（如果有）。如果没有，则分割是最优的，因此直接返回 false。
		 */
		fc_v->spl_dontcare = (bool *) palloc0(sizeof(bool) * (fc_entryvec->n + 1));

		fc_NumDontCare = fc_findDontCares(fc_r, fc_giststate, fc_entryvec->vector, fc_v, fc_attno);

		if (fc_NumDontCare > 0)
		{
			/*
			 * 从 spl_left[] 和 spl_right[] 中移除不关心的元组。
			 */
			fc_removeDontCares(fc_sv->spl_left, &fc_sv->spl_nleft, fc_v->spl_dontcare);
			fc_removeDontCares(fc_sv->spl_right, &fc_sv->spl_nright, fc_v->spl_dontcare);

			/*
			 * 如果任一侧的所有元组都是不关心的，则分割是
			 * 简单的，最好忽略它并在下一个列上进行分割。 （我们曾试图通过强制
			 * 每侧的随机元组被视为非不关心的来继续进行次级分割，但这项技术
			 * 似乎不太可能真正提供更好的结果。 请注意，我们不想尝试
			 * 在空的左或右主分割侧进行次级分割，因为那样在该侧就没有
			 * 联合键供 PickSplit 函数尝试扩展，因此它无法对其操作给出
			 * 良好的优点指标。 另请注意，此检查确保我们不能在下面的
			 * NumDontCare == 1 特殊情况下产生虚假的单侧分割。）
			 */
			if (fc_sv->spl_nleft == 0 || fc_sv->spl_nright == 0)
			{
				fc_v->spl_dontcare = NULL;
				return true;
			}

			/*
			 * 重新计算联合键，仅考虑非不关心元组。
			 * 注意：这将为剩余的索引列设置联合键，
			 * 这将导致后续对 gistUserPicksplit 的调用将这些
			 * 值传递给用户定义的 PickSplit 方法，其中
			 * spl_ldatum_exists/spl_rdatum_exists 设置为 true。
			 */
			fc_gistunionsubkey(fc_giststate, fc_itup, fc_v);

			if (fc_NumDontCare == 1)
			{
				/*
				 * 如果只有一个不关心元组，那么我们不能对其进行
				 * PickSplit，因此只需通过比较惩罚选择将其发送到左侧还是
				 * 右侧。 无论如何，我们需要 gistunionsubkey 步骤，这样
				 * 我们就有适当的联合键来计算惩罚。
				 */
				OffsetNumber fc_toMove;

				/* 找到它... */
				for (fc_toMove = FirstOffsetNumber; fc_toMove < fc_entryvec->n; fc_toMove++)
				{
					if (fc_v->spl_dontcare[fc_toMove])
						break;
				}
				Assert(fc_toMove < fc_entryvec->n);

				/* ...并将其分配给较便宜的一侧 */
				fc_placeOne(fc_r, fc_giststate, fc_v, fc_itup[fc_toMove - 1], fc_toMove, fc_attno + 1);

				/*
				 * 此时联合键是错误的，但我们不在意
				 * 因为我们已经完成了分割。 gistSplitByKey 的
				 * 最外层递归级别将在返回之前修复它。
				 */
			}
			else
				return true;
		}
	}

	return false;
}

/*
 * 简单地将页面一分为二
 */
static void fc_gistSplitHalf(GIST_SPLITVEC *fc_v, int fc_len)
{
	int			fc_i;

	fc_v->spl_nright = fc_v->spl_nleft = 0;
	fc_v->spl_left = (OffsetNumber *) palloc(fc_len * sizeof(OffsetNumber));
	fc_v->spl_right = (OffsetNumber *) palloc(fc_len * sizeof(OffsetNumber));
	for (fc_i = 1; fc_i <= fc_len; fc_i++)
		if (fc_i < fc_len / 2)
			fc_v->spl_right[fc_v->spl_nright++] = fc_i;
		else
			fc_v->spl_left[fc_v->spl_nleft++] = fc_i;

	/* 我们不需要计算联合键，调用者已经处理了它 */
}

/*
 * gistSplitByKey：页面分割算法的主要入口点
 *
 * r：索引关系
 * page：被分割的页面
 * itup：待处理的 IndexTuples 数组
 * len：待处理的 IndexTuples 数量（必须至少为 2）
 * giststate：关于索引的附加信息
 * v：工作状态和输出区域
 * attno：我们正在处理的列（零基索引）
 *
 * 外部调用者必须将 v->spl_lisnull 和 v->spl_risnull 数组初始化为全真。
 * 返回时，spl_left/spl_nleft 包含要向左移动的元组索引，
 * spl_right/spl_nright 包含要向右移动的元组索引，
 * spl_lattr/spl_lisnull 包含左侧联合键值，
 * 而 spl_rattr/spl_risnull 包含右侧联合键值。 
 * 此结构中的其他字段是该文件的工作区。
 *
 * 外部调用者必须将 attno 传递为零。 该函数可能会通过传递 attno+1 进行内部递归
 * 到下一个列。
 */
void gistSplitByKey(Relation fc_r, Page fc_page, IndexTuple *fc_itup, int fc_len,
			   GISTSTATE *fc_giststate, GistSplitVector *fc_v, int fc_attno)
{
	GistEntryVector *fc_entryvec;
	OffsetNumber *fc_offNullTuples;
	int			fc_nOffNullTuples = 0;
	int			fc_i;

	/* 生成项目数组，并识别具有空键的元组 */
	/* 请注意 entryvec->vector[0] 在此代码中未使用 */
	fc_entryvec = palloc(GEVHDRSZ + (fc_len + 1) * sizeof(GISTENTRY));
	fc_entryvec->n = fc_len + 1;
	fc_offNullTuples = (OffsetNumber *) palloc(fc_len * sizeof(OffsetNumber));

	for (fc_i = 1; fc_i <= fc_len; fc_i++)
	{
		Datum		fc_datum;
		bool		fc_IsNull;

		fc_datum = index_getattr(fc_itup[fc_i - 1], fc_attno + 1, fc_giststate->leafTupdesc,
							  &fc_IsNull);
		gistdentryinit(fc_giststate, fc_attno, &(fc_entryvec->vector[fc_i]),
					   fc_datum, fc_r, fc_page, fc_i,
					   false, fc_IsNull);
		if (fc_IsNull)
			fc_offNullTuples[fc_nOffNullTuples++] = fc_i;
	}

	if (fc_nOffNullTuples == fc_len)
	{
		/*
		 * 边缘情况：attno列中的所有键都是null，因此只需将
		 * 我们的注意力转向下一列。如果没有下一列，则仅将页面一分为二。
		 */
		fc_v->spl_risnull[fc_attno] = fc_v->spl_lisnull[fc_attno] = true;

		if (fc_attno + 1 < fc_giststate->nonLeafTupdesc->natts)
			gistSplitByKey(fc_r, fc_page, fc_itup, fc_len, fc_giststate, fc_v, fc_attno + 1);
		else
			fc_gistSplitHalf(&fc_v->splitVector, fc_len);
	}
	else if (fc_nOffNullTuples > 0)
	{
		int			fc_j = 0;

		/*
		 * 我们不想在一个页面上混合NULL和非NULL键，因此将
		 * null值放到右侧页面，将非null值放到左侧页面。
		 */
		fc_v->splitVector.spl_right = fc_offNullTuples;
		fc_v->splitVector.spl_nright = fc_nOffNullTuples;
		fc_v->spl_risnull[fc_attno] = true;

		fc_v->splitVector.spl_left = (OffsetNumber *) palloc(fc_len * sizeof(OffsetNumber));
		fc_v->splitVector.spl_nleft = 0;
		for (fc_i = 1; fc_i <= fc_len; fc_i++)
			if (fc_j < fc_v->splitVector.spl_nright && fc_offNullTuples[fc_j] == fc_i)
				fc_j++;
			else
				fc_v->splitVector.spl_left[fc_v->splitVector.spl_nleft++] = fc_i;

		/* 计算联合键，除非外部递归级别会处理它 */
		if (fc_attno == 0 && fc_giststate->nonLeafTupdesc->natts == 1)
		{
			fc_v->spl_dontcare = NULL;
			fc_gistunionsubkey(fc_giststate, fc_itup, fc_v);
		}
	}
	else
	{
		/*
		 * 所有键都是非空的，因此应用用户定义的PickSplit方法
		 */
		if (fc_gistUserPicksplit(fc_r, fc_entryvec, fc_attno, fc_v, fc_itup, fc_len, fc_giststate))
		{
			/*
			 * 在attno列上拆分并不是最优的，因此考虑根据下一列
			 * 重新分配不关心的元组
			 */
			Assert(fc_attno + 1 < fc_giststate->nonLeafTupdesc->natts);

			if (fc_v->spl_dontcare == NULL)
			{
				/*
				 * 此拆分实际上是退化的，因此完全忽略它
				 * 仅根据下一列进行拆分。
				 */
				gistSplitByKey(fc_r, fc_page, fc_itup, fc_len, fc_giststate, fc_v, fc_attno + 1);
			}
			else
			{
				/*
				 * 形成一个仅包含不关心元组的数组，以便传递给
				 * 此函数的递归调用以处理下一列。
				 */
				IndexTuple *fc_newitup = (IndexTuple *) palloc(fc_len * sizeof(IndexTuple));
				OffsetNumber *fc_map = (OffsetNumber *) palloc(fc_len * sizeof(OffsetNumber));
				int			fc_newlen = 0;
				GIST_SPLITVEC fc_backupSplit;

				for (fc_i = 0; fc_i < fc_len; fc_i++)
				{
					if (fc_v->spl_dontcare[fc_i + 1])
					{
						fc_newitup[fc_newlen] = fc_itup[fc_i];
						fc_map[fc_newlen] = fc_i + 1;
						fc_newlen++;
					}
				}

				Assert(fc_newlen > 0);

				/*
				 * 备份v->splitVector的副本，因为递归
				 * 调用会用其自己的结果覆盖它。
				 */
				fc_backupSplit = fc_v->splitVector;
				fc_backupSplit.spl_left = (OffsetNumber *) palloc(sizeof(OffsetNumber) * fc_len);
				memcpy(fc_backupSplit.spl_left, fc_v->splitVector.spl_left, sizeof(OffsetNumber) * fc_v->splitVector.spl_nleft);
				fc_backupSplit.spl_right = (OffsetNumber *) palloc(sizeof(OffsetNumber) * fc_len);
				memcpy(fc_backupSplit.spl_right, fc_v->splitVector.spl_right, sizeof(OffsetNumber) * fc_v->splitVector.spl_nright);

				/* 递归决定如何拆分不关心的元组 */
				gistSplitByKey(fc_r, fc_page, fc_newitup, fc_newlen, fc_giststate, fc_v, fc_attno + 1);

				/* 将子拆分的结果与非不关心元组合并 */
				for (fc_i = 0; fc_i < fc_v->splitVector.spl_nleft; fc_i++)
					fc_backupSplit.spl_left[fc_backupSplit.spl_nleft++] = fc_map[fc_v->splitVector.spl_left[fc_i] - 1];
				for (fc_i = 0; fc_i < fc_v->splitVector.spl_nright; fc_i++)
					fc_backupSplit.spl_right[fc_backupSplit.spl_nright++] = fc_map[fc_v->splitVector.spl_right[fc_i] - 1];

				fc_v->splitVector = fc_backupSplit;
			}
		}
	}

	/*
	 * 如果我们正在处理一个多列索引，在递归结束时
	 * 重新计算所有索引列的左右联合数据。这样
	 * 可以确保在所有边缘情况下返回正确的联合数据，
	 * 包括当我们在开始时没有处理所有列，或者
	 * 当二次拆分将“不关心”的元组从一侧移动到另一侧
	 * （我们真的不应该假设这不会改变联合数据）。
	 *
	 * 注意：当我们处于内部递归（attno > 0）时，我们不担心
	 * 返回的联合数据是否合理，因为调用级别不会关心。
	 * 此外，在单列索引中，我们期望
	 * PickSplit（或上述特例）产生正确的联合
	 * 数据。
	 */
	if (fc_attno == 0 && fc_giststate->nonLeafTupdesc->natts > 1)
	{
		fc_v->spl_dontcare = NULL;
		fc_gistunionsubkey(fc_giststate, fc_itup, fc_v);
	}
}
